翻訳と辞書 Words near each other ・ No Fixed Address ・ No Fixed Address (album) ・ No Fixed Address Tour ・ No Flex Zone ・ No Fly List ・ No Fog West Theater Company ・ No Fond Return of Love ・ No Fool No More ・ No Fools, No Fun ・ No For An Answer ・ No for an Answer ・ No Format! ・ No Fraud ・ No Free Lunch (organization) ・ No free lunch in search and optimization ・ No free lunch theorem ・ No free lunch with vanishing risk ・ No Freedom ・ No Friends ・ No Friends of Harry ・ No frills ・ No Frills (Bette Midler album) ・ No frills (disambiguation) ・ No Frills (grocery store) ・ No Frills (Nik Kershaw album) ・ No Frills (TV series) ・ No Frills Excursions ・ No Frills Friend ・ No Frills Love ・ No Frills Prison Act Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク No free lunch theorem ： ウィキペディア英語版 No free lunch theorem In mathematical folklore, the "no free lunch" theorem (sometimes pluralized) of David Wolpert and William Macready appears in the 1997 "No Free Lunch Theorems for Optimization".〔Wolpert, D.H., Macready, W.G. (1997), "(No Free Lunch Theorems for Optimization )", ''IEEE Transactions on Evolutionary Computation'' 1, 67.〕 Wolpert had previously derived no free lunch theorems for machine learning (statistical inference).〔Wolpert, David (1996), "(The Lack of ''A Priori'' Distinctions between Learning Algorithms )", ''Neural Computation'', pp. 1341-1390.〕 In 2005, Wolpert and Macready themselves indicated that the first theorem in their paper "state() that any two optimization algorithms are equivalent when their performance is averaged across all possible problems".〔Wolpert, D.H., and Macready, W.G. (2005) "Coevolutionary free lunches", ''IEEE Transactions on Evolutionary Computation'', 9(6): 721-735〕 The 1997 theorems of Wolpert and Macready are mathematically technical and some find them unintuitive. The folkloric "no free lunch" (NFL) theorem is an easily stated and easily understood consequence of theorems Wolpert and Macready actually prove. It is weaker than the proven theorems, and thus does not encapsulate them. Various investigators have extended the work of Wolpert and Macready substantively. See No free lunch in search and optimization for treatment of the research area. ==Original NFL theorems== Wolpert and Macready give two NFL theorems that are closely related to the folkloric theorem. In their paper, they state: The theorem first hypothesizes objective functions that do not change while optimization is in progress, and the second hypothesizes objective functions that may change.〔 :''Theorem 1'': For any algorithms ''a''1 and ''a''2, at iteration step ''m'' ::$\backslash sum\_f\; P(d\_m^y\; |\; f,\; m,\; a\_1)\; =\; \backslash sum\_f\; P(d\_m^y\; |\; f,\; m,\; a\_2),$ where $d\_m^y$ denotes the ordered set of size $m$ of the cost values $y$ associated to input values $x\; \backslash in\; X$, $f:X\; \backslash rightarrow\; Y$ is the function being optimized and $P(d\_m^y\; |\; f,\; m,\; a)$ is the conditional probability of obtaining a given sequence of cost values from algorithm $a$ run $m$ times on function $f$. The theorem can be equivalently formulated as follows: :''Theorem 1'': Given a finite set $V$ and a finite set $S$ of real numbers, assume that $f\; :\; V\; \backslash to\; S$ is chosen at random according to uniform distribution on the set $V^S$ of all possible functions from $V$ to $S$. For the problem of optimizing $f$ over the set $V$, then no algorithm performs better than blind search. Here, ''blind search'' means that at each step of the algorithm, the element $v\; \backslash in\; V$ is chosen at random with uniform probability distribution from the elements of $V$ that have not been chosen previously. In essence, this says that when all functions ''f'' are equally likely, the probability of observing an arbitrary sequence of ''m'' values in the course of optimization does not depend upon the algorithm. In the analytic framework of Wolpert and Macready, performance is a function of the sequence of observed values (and not e.g. of wall-clock time), so it follows easily that all algorithms have identically distributed performance when objective functions are drawn uniformly at random, and also that all algorithms have identical mean performance. But identical mean performance of all algorithms does not imply Theorem 1, and thus the folkloric theorem is not equivalent to the original theorem. Theorem 2 establishes a similar, but "more subtle", NFL result for time-varying objective functions.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「No free lunch theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.